/*
 * @lc app=leetcode.cn id=1220 lang=cpp
 *
 * [1220] 统计元音字母序列的数目
 */

// @lc code=start
class Solution
{
public:
    int countVowelPermutation(int n)
    {
        int mod = 1e9 + 7;
        // 初始化，当前状态
        vector<long long> dp(5, 1);
        // 下一次状态
        vector<long long> dpn(5, 0);

        for (int i = 2; i <= n; i++)
        {
            // 当前状态
            dpn[0] = (dp[1] + dp[2] + dp[4]) % mod;
            dpn[1] = (dp[0] + dp[2]) % mod;
            dpn[2] = (dp[1] + dp[3]) % mod;
            dpn[3] = (dp[2]);
            dpn[4] = (dp[2] + dp[3]) % mod;

            // 下一次状态
            dp = dpn;
        }

        int ans = 0;
        for (int i = 0; i < 5; i++)
        {
            ans = (ans + dp[i]) % mod;
        }

        return ans;
    }
};
// @lc code=end
